//priority queue
#include <vector>

template<typename type>
class priorityQueue {
public:
	priorityQueue() {
		pque.push_back(type()); priority.push_back(0);
	}
	priorityQueue(const vector<pair<int, type>> &newque) {
		pque.push_back(type()); priority.push_back(newque.size());
		for (auto item : newque) {
			push(item.second, item.first);
		}
	}
	void push(const type &item, int pr);
	void pop();
	void clear();
	type front();
	bool empty();
	unsigned size();
protected:
	void heapAdjustUp();
	void heapAdjustDown();
private:
	vector<type> pque;
	vector<int> priority;
};

template<typename type>
void priorityQueue<type>::push(const type &item, int pr) {
	pque.push_back(item); priority.push_back(pr);
	++priority[0];
	heapAdjustUp();
}
template<typename type>
void priorityQueue<type>::pop() {
	if (empty()) return;
	pque[1] = pque.back(); priority[1] = priority.back();
	pque.pop_back(); priority.pop_back();
	--priority[0];
	heapAdjustDown();
}
template<typename type>
void priorityQueue<type>::clear() {
	pque.clear(); priority.clear();
	pque.push_back(type()); priority.push_back(0);
}
template<typename type>
type priorityQueue<type>::front() {
	if (empty()) return type();
	return pque[1];
}
template<typename type>
bool priorityQueue<type>::empty() {
	if (size())
		return false;
	else
		return true;
}
template<typename type>
unsigned priorityQueue<type>::size() {
	return priority.front();
}
template<typename type>
void priorityQueue<type>::heapAdjustUp() {
	int cur = size();
	int save_pr = priority[cur];
	type save_val = pque[cur];
	for (int i = cur / 2; i != 0; i /= 2) {
		if (save_pr > priority[i]) {
			priority[cur] = priority[i]; pque[cur] = pque[i];
			cur = i;
		}
		else
			break;
	}
	priority[cur] = save_pr; pque[cur] = save_val;
}
template<typename type>
void priorityQueue<type>::heapAdjustDown() {
	if (empty()) return;
	int length = size(), save_pr = priority[1], cur = 1;
	type save_val = pque[1];
	for (int i = cur * 2; i <= length; i *= 2) {
		if (i < length && priority[i] < priority[i+1])
			++i;
		if (save_pr < priority[i]) {
			priority[cur] = priority[i]; pque[cur] = pque[i];
			cur = i;
		}
		else
			break;
	}
	priority[cur] = save_pr; pque[cur] = save_val;
}